翻訳と辞書 Words near each other ・ Chomphet District ・ Chomphu ・ Chomphu, Lampang ・ Chomphu, Phitsanulok ・ Chompion ・ Chompon Buangam ・ Chompoo Sangpo ・ Chomranice ・ Chomrieng Et Preang Tuok ・ Chomski ・ Chomsky (band) ・ Chomsky (disambiguation) ・ Chomsky (surname) ・ Chomsky hierarchy ・ Chomsky normal form ・ Chomsky–Schützenberger enumeration theorem ・ Chomsky–Schützenberger representation theorem ・ Chomsky–Schützenberger theorem ・ Chomu ・ Chomu (Rajasthan Assembly constituency) ・ Chomukha Bhairavji Temple ・ Chomutice ・ Chomutov ・ Chomutov District ・ Chomutov Zoo ・ Chomutov–Vejprty/Reitzenhain railway ・ Chomérac ・ Chomýž ・ Chomątowo ・ Chomęc Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Chomsky–Schützenberger enumeration theorem ： ウィキペディア英語版 Chomsky–Schützenberger enumeration theorem In formal language theory, the Chomsky–Schützenberger enumeration theorem is a theorem derived by Noam Chomsky and Marcel-Paul Schützenberger about the number of words of a given length generated by an unambiguous context-free grammar. The theorem provides an unexpected link between the theory of formal languages and abstract algebra. ==Statement== In order to state the theorem, a few notions from algebra and formal language theory are needed. A ''power series'' over $\backslash mathbb$ is an infinite series of the form :$f\; =\; f(x)\; =\; \backslash sum\_^\backslash infty\; a\_k\; x^k\; =\; a\_0\; +\; a\_1\; x^1\; +\; a\_2\; x^2\; +\; a\_3\; x^3\; +\; \backslash cdots$ with coefficients $a\_k$ in $\backslash mathbb$. The ''multiplication'' of two formal power series $f$ and $g$ is defined in the expected way as the convolution of the sequences $a\_n$ and $b\_n$: :$f(x)\backslash cdot\; g(x)\; =\; \backslash sum\_^\backslash infty\; \backslash left(\backslash sum\_^k\; a\_i\; b\_\backslash right)\; x^k.$ In particular, we write $f^2\; =\; f(x)\backslash cdot\; f(x)$, $f^3\; =\; f(x)\backslash cdot\; f(x)\backslash cdot\; f(x)$, and so on. In analogy to algebraic numbers, a power series $f(x)$ is called ''algebraic'' over $\backslash mathbb(x)$, if there exists a finite set of polynomials $p\_0(x),\; p\_1(x),\; p\_2(x),\; \backslash ldots\; ,\; p\_n(x)$ each with rational coefficients such that :$p\_0(x)\; +\; p\_1(x)\; \backslash cdot\; f\; +\; p\_2(x)\backslash cdot\; f^2\; +\; \backslash cdots\; +\; p\_n(x)\backslash cdot\; f^n\; =\; 0.$ A context-free grammar is said to be ''unambiguous'' if every string generated by the grammar admits a unique parse tree or, equivalently, only one leftmost derivation. Having established the necessary notions, the theorem is stated as follows. :Chomsky–Schützenberger theorem. If $L$ is a context-free language admitting an unambiguous context-free grammar, and $a\_k\; :=\; |\; L\; \backslash \; \backslash cap\; \backslash Sigma^k\; |$ is the number of words of length $k$ in $L$, then $G(x)=\backslash sum\_^\backslash infty\; a\_k\; x^k$ is a power series over $\backslash mathbb$ that is algebraic over $\backslash mathbb(x)$. Proofs of this theorem are given by , and by . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chomsky–Schützenberger enumeration theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.